package com.sise.Array;

import java.util.ArrayList;
import java.util.List;

/**
 *      119. 杨辉三角 II
 *      给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
 *      输入: 3
 *      输出: [1,3,3,1]
 */
public class _119_getRow {

    /**
     *      解法一：只用一个数组，从尾部向前遍历
     */
    public List<Integer> getRow(int rowIndex) {
        List<Integer> result = new ArrayList<>();
        result.add(1);                          // 第一行
        for (int i = 1; i <= rowIndex; i++){    // 从第一行开始
            result.add(0);                      // 在末尾 +0，使得两位相加流程 走通
            for (int j = i; j > 0; j--){        // 从尾部向前循环，这也是为什么需要 +0 的原因
                result.set(j, result.get(j) + result.get(j - 1));   // 设置相关位置的数值
            }
        }
        return result;
    }

    /**
     *      解法二：滚动数组
     */
    public List<Integer> getRow_2(int rowIndex) {
        List<Integer> oldList = new ArrayList<>();

        for (int i = 0; i <= rowIndex; i++) {   // 这里需要等于号，因为题目中实际上表达的是第四行
            List<Integer> newList = new ArrayList<>();  // newList 需要每次循环都进行创建，如果是全局变量会有脏数据
            for (int j = 0; j <= i; j++) {      // 这里是等于号
                if (j == 0 || j == i) {         // 代表最左、最右边的 1
                    newList.add(1);
                } else {
                    newList.add(oldList.get(j) + oldList.get(j - 1));    // 由上一层相加
                }
            }
            oldList = newList;
        }
        return oldList;
    }
}
